package com.melo;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 弗洛伊德算法: 计算各个村庄到其他村庄的最短距离
 * @date 2025-06-12
 */
public class Floyd {

    public void floyd(FloydVillageGraph graph) {
        // 保存距离
        int distance = 0;
        // 遍历中间顶点, k就是中间顶点的下标 [A, B, C, D, E, F, G]
        for (int k = 0; k < graph.getDistanceMatrixArr().length; k++) {
            // 从i顶点开始出发 [A, B, C, D, E, F, G]
            for (int i = 0; i < graph.getDistanceMatrixArr().length; i++) {
                // 到达j顶点 [A, B, C, D, E, F, G]
                for (int j = 0; j < graph.getDistanceMatrixArr().length; j++) {
                    // 求出从i顶点出发，经过k中间顶点，到达j顶点距离
                    distance = graph.getDistanceMatrixArr()[i][k] + graph.getDistanceMatrixArr()[k][j];
                    if (distance < graph.getDistanceMatrixArr()[i][j]) {
                        // 如果distance小于dis[i][j]
                        graph.getDistanceMatrixArr()[i][j] = distance;
                        // 更新前驱顶点
                        graph.getPreVillageVertexMatrixArr()[i][j] = graph.getPreVillageVertexMatrixArr()[k][j];
                    }
                }
            }
        }
    }
}
